/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    void run(TreeNode *root){
        if (root==NULL) return;
        run(root->left);
        run(root->right);
        TreeNode *tmp=root->left;
        root->left=NULL;
        if (tmp!=NULL) {
            tmp->left->right=root->right;
            if (root->right!=NULL) tmp->left=root->right->left;
        } else tmp=root->right;
        if (tmp==NULL)
            root->left=root;
        else {
            root->right=tmp;
            root->left=tmp->left;
        }
    }
public:
    void flatten(TreeNode *root) {
        run(root);
        while (root!=NULL) {
            root->left=NULL;
            root=root->right;
        }
    }
};
